1. Field of the Invention
The present invention relates to a combinational circuit, and an encoder, a decoder and a semiconductor device that use this combinational circuit. More specifically, the present invention relates to a combinational circuit that can effectively correct errors, especially in a fast optical communication field, and an encoder, a decoder and a semiconductor device that use this combinational circuit.
2. Brief Description of the Prior Art
Importance of Fast and Superior Error Correction Technique
In consonance with the expansion of the Internet and the development of e-business, the rate of increase in the volume of data computers can handle and their speed has accelerated. Accordingly, there is a demand for increasing speed of data transfer among computers, and in line with this demand, optical communication that yields transfer speed of up to 40 Gbps is becoming popular. However, for such a fast communication method such as the optical communication method, to maintain an acceptable error rate at system level requires that the reliability of data communication be further increased in proportion to the amount of data processed by a computer.
Important techniques, called error correction coding techniques, have been devised to improve data reliability employing high-level mathematics to automatically correct errors caused by a variety of factors (e.g., noise along a channel). Popular known techniques are Hamming code and Reed-Solomon code, both of which are frequently employed. Basically, Hamming codes correct single bit errors, but their correction capability is low. For instance, with Hamming codes, if a single bit error is detected, the error is corrected, but if the detected error covers two bits, only the error detection portion of the process is performed, no correction is made. However, setting up an error correction process for an error correction system using Hamming code is simple, and it is well known that by performing the error correction process in parallel, a processing speed that greatly exceeds 1 Gbps (one billion bits per second) can be obtained.
On the other hand, Reed-Solomon code is a superior error correction technique possessing high correction capabilities and can be used to correct errors appearing as units (symbols) comprising multiple contiguous bits. At present, however, because of the complicated calculations that are frequently required, using Reed-Solomon code to perform correction processes in parallel is difficult; and even when pipeline processes using data having eight-bit width are performed at 100 MHz, for example, only processing speed of around 800 Mb/s can be obtained. Currently, therefore, since the speed attainable with conventional techniques using Reed-Solomon codes is not suitable for fields in which high processing speed is required, these techniques are employed mainly for fields to which comparatively low data processing speed is acceptable, such as the low speed communication field and the data storage-unit field for the production of hard disks or secondary storage devices, CD-ROMs, for example.
Error Correction Technique Required by a Fast Optical Communication Field
As part of a fast optical communication technique for data communication by computers, by the recently popular Internet as a backbone, a terabit per second fast communication system that employs WDM (Wavelength Division Multiplexing) and DWDM (Dense WDM), which has improved wavelength division multiplexing levels, has been introduced based on the SONET technique, according to which frames having a predetermined length are synchronously and sequentially transmitted.
As the wavelength division multiplexing levels for the above described optical data communication is increased, crosstalk occurs between wavelengths that are near each other. To cope with this crosstalk, FEC (Forward Error Correction) is employed as an error correction method for communication in long distance (Long Haul) optical wavelength division multiplexing. In ITU-T G.975, the ITU (International Telecommunication Union) standardized the use of interleaved (255, 239)RS code (code length n=255 bytes) of m=8 (8 bits/symbols), and in G.709, the Digital Wrapper standard for defining the FEC frame structure is employed.
According to the Digital Wrapper standard, for example, low-speed serial Reed-Solomon code circuits are arranged in parallel to achieve a necessary processing capability, and for this, interleaving of Reed-Solomon codes is an indispensable technique.
Prior Art for Fast and High-Level Error Correction Techniques
Independent of the need for optical communication, parallel fast decoding using Reed-Solomon code has been studied using a combinational circuit.
FIG. 1 is a diagram showing an example of a fast decoder that can be used for an error correction apparatus. The decoding circuit in FIG. 1 implements a procedure for increasing by a multiple of ten or more the decoding speed of one decoding circuit, and for performing, at substantially the comparable speed as that of Humming code, parallel decoding in an error correction process using the Reed-Solomon coding possessing high-level error correction capabilities. For the decoding circuit in FIG. 1, a new representation using the elementary symmetric functions is employed for decoding Reed-Solomon codes, so that an error value polynomial Er(x) of 0(t)-degree with which error values can be directly calculated is employed (t is the maximum number of correctable errors).
Since the decoding circuit in FIG. 1 employs this polynomial, not only syndrome calculation and error location evaluation, but also error value evaluation can be directly obtained by performing calculations for a single polynomial. Therefore, compared with the conventional methods whereby these calculations are performed by Forney algorithm to divide evaluation results obtained for two polynomials, a greatly simplified operation can be used. Further, in the decoding circuit in FIG. 1, a representation appropriate for a combinational circuit is employed not only for the calculation of the coefficients of Er(x), but also for the calculation of the coefficients of the error locator polynomial Λ(x), so that not only can a higher processing speed be provided, but in addition, the number of required arithmetic circuits can be reduced.
When the decoding circuit in FIG. 1 is employed, a random 4-byte error correction circuit, which is mounted on an experimental base for a semiconductor using the standard 0.35 μm ASIC technique, can process in parallel, and at a low latency (45 ns), data having a 320-bit width, and a processing speed of 7 Gb/s (7 billion bits per second) can be obtained that is nearly ten times higher than the typical processing speed of 800 Mb/s available with a current serial decoding circuit. In addition, when a new circuit optimization algorithm specifically prepared for a large parallel error correction circuit and a circuit sharing method are employed for the decoding circuit in FIG. 1, the circuit size can be reduced. And furthermore, since the decoding circuit in FIG. 1 is a combinational circuit that does not require an external controller and registers, in spite of the high processing speed that can be attained, power consumption can be reduced.
However, the decoding circuit in FIG. 1 can not provide a processing speed that equals 40 Gbps required for optical communication, and in order to cope with the 8-byte error correction standard established by the ITU, when the normal circuit sharing method is used the resulting circuit can be so large that it can not be mounted on a single chip.
FIG. 2 is a schematic diagram showing the configuration of an error correction circuit that employs a conventional low-speed decoding method for optical communication. With this configuration, as the communication speed of an optical communication field increases, the conventional method whereby low-speed serial Reed-Solomon decoders are arranged in parallel becomes ever more inappropriate. Through conventional RS decoders have a processing speed below 1 Gbps, the decoding method in FIG. 2 achieves the necessary processing speed by an appropriate arrangement of low-speed serial Reed-Solomon decoders. However, according to the conventional method in FIG. 2, for such an arrangement of many Reed-Solomon decoders are required, and accordingly, the circuit size is increased in direct proportion to the data transfer speed used for optical communication. FIG. 3 is a graph showing circuit size and data transfer speed plotted when the decoding method in FIG. 2 is employed.
FIG. 4 is a diagram showing another conventional decoding circuit (A. Patel, IBM J. Res. Develop., vol. 30, pp. 259–269, 1986). Since according to this conventional decoding method, the processing speed can be easily increased for the calculation of syndromes and error locations. However, since as is shown in FIG. 4 Forney algorithm is employed for the calculation of error value, two polynomials, i.e., the differential dΛ(x)/dx for the error locator polynomial and the error evaluator polynomial Ω(x), which are obtained by the syndromes and the error locator polynomial, must be evaluated, and then divisions must be performed. This is a critical path that prevents an increase in output speed, and the processing speed can not be satisfactorily increased.
According to OC-768 SONET, this is a large problem, because assuming the 16 interleave defined by ITU-G709 is employed as an input/output interface for the decoding circuit, a fast processing speed of 300 MHz or higher is expected. Therefore, as one attempt, the decoder in FIG. 4 is employed and divisions corresponding to the critical path are converted into detailed pipelines to increase output speed.
However, even when the process is converted into a pipeline, the decoding circuit in FIG. 4 must perform divisions at locations whereat no error is present, and the circuit size and the power consumption are increased as the pipeline is constructed. Further, to perform divisions only for error locations, the locations must be calculated in advance, so that the error locations and the error values can not be calculated in parallel. In addition, for the decoding circuit in FIG. 4, a cycle count required for the output of the error values differs depending on whether an error is present. Therefore, when a synchronous frame, such as SONET, for sequential data must be input or output at high speed, it is difficult to output error values at high speed for a constant cycle, without depending on error patterns (number of errors and their locations).
FIG. 5 is a diagram showing an additional conventional decoder. When the parallel Reed-Solomon decoding method in FIG. 1 is employed for the optical communication field, because its circuit processing capability is superior to those of other conventional methods no problem occurs when non-interleaved RS code is used for an application. However, for interleaved Reed-Solomon codes, as defined by ITU-T G.975, since signals must be rearranged using a large, high-speed buffer and selector, the parallel Reed-Solomon decoding method is not always efficient. That is, the length of (255, 239)RS code is 2040 bits, and when a 16-byte interleaving process is performed, a 16-byte input and 255-byte output serial/parallel converter and a parallel/serial converter for a 255-byte input and a 16-byte output are required, thereby considerably increasing the size of a circuit even though the processing speed can be increased to a required level. Therefore, it is difficult for the parallel Reed-Solomon decoding method to he provided at a practical level for optical communication.
For the calculation of error locations and error values used for the decoder, a large number of calculations in the Galois extension field GF(2m) must be performed at high speed, and further, the size of a circuit that can perform this processing must be such that it facilitates the implementation of the circuit. Conventionally, in the studies of the calculations over a Galois field, it is important that how efficiently a single calculation (multiplication or division) can be performed, and the several tens to hundreds of calculations by a combinational circuit have almost never been discussed to date. As one of various reasons this has not been done, it may be presumed many decoding operations tend to be performed by sequential circuits, and it has been ascertained that the use of a combinational circuit provides little merit in terms of processing capabilities and an acceptable circuit size.
During the studies of the error correction calculation algorithm, the Yule-Walker equation that is defined for the Galois extension field GF(2m) is generated in decoding of the Reed-Solomon codes. The efficient processing of this Yule-Walker equation is desirable if high-speed processing is to be achieved and the size of the necessary circuit is to be minimized. When the algorithm for solving the Yule-Walker equation is performed by a combinational circuit to achieve high-speed processing, in as the required error correction capabilities increase, the portion of the circuit used to solve the Yule-Walker equation and to locate errors becomes very significant from the viewpoint of the reduction in the size of the combinational circuit.
In addition, when a combinational circuit that can carry out the decoding of Reed-Solomon codes is applied for an actual system, it is preferable that an algorithm be provided that can be applied for the decoding of Reed-Solomon codes having an arbitrary minimum distance in order to obtain a process that can be widely used and to remove superfluous, additional circuits or processes. Especially in the optical communication field, since the use of (255, 239) Reed-Solomon code is standardized by the ITU, an algorithm is required that can efficiently decode the Reed-Solomon code where the maximum number of correctable errors is 8 and the minimum distance is 17.
In order to solve the mathematical problem posed by the Yule-Walker equation by using a hardware combinational circuit having a size that permits it to be implemented, increase in the circuit size must be suppressed, and an algorithm that can reduce the number of multipliers and a combinational circuit that can efficiently employ this algorithm are required. That is, a combinational circuit is needed that has an implementable size and that performs high-speed processing, and that includes the error correction device and the error correction algorithm described above.